//一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
// Related Topics 位运算 数组 哈希表 数学 二分查找 👍 269 👎 0

package leetcode.editor.cn;

class QueShiDeShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new QueShiDeShuZiLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 二分查找
         *  时间复杂度 O(\log N)O(logN)： 二分法为对数级别复杂度。
         * 空间复杂度 O(1)O(1)： 几个变量使用常数大小的额外空间。
         * @param nums
         * @return
         */
        /*public int missingNumber(int[] nums) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = (right - left) / 2;
                if (nums[mid] == mid) { // 是否等于索引
                    left = mid + 1;
                } else right = mid - 1;
            }

            return nums[left];
        }*/

        /**
         * 哈希表
         *
         * @param nums
         * @return
         */
        public int missingNumber(int[] nums) {
            int[] array = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                array[nums[i]] = 1;
            }

            int result = 0;

            for (int i = 0; i < array.length; i++) {
                if (array[i] != 1) {
                    result = i;
                    break;
                }
            }

            return result;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
